package setCoveringProblem.concurrente;
/* $Id: Cover.java 2844 2004-11-24 10:52:27Z ceriel $ */

/**
 * Esta versión nace de la versión secuencial:
 * setCoveringProblem.modificado.Cover
 */

/** 
 * Imports relacionados con esta versión concurrente 
 */
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

/**
 * Implementamos la interfaz Callable, parametrizada con {@link Return} ya 
 * que será el tipo del objeto de retorno de los hilos.
 */
public final class Cover implements Callable<Return>{

	/**
	 * Se vuelve a utilizar un umbral, al igual que en la versión 
	 * gridificada. Con este umbral se evita paralelizar procesamiento 
	 * trivial.
	 */
	static final int THRESHOLD = 15;
	
	/**
	 * Utilizo un solo pool de threads para todas las instancias. 
	 * Ver {@link adaptiveIntegration.concurrente.AdapInt#pool}
	 */
    private static ExecutorService pool=null;
	
	/**
	 * Variables de instancia que encapsulan los valores de entrada del 
	 * algoritmo. Permitirán llamar al call() sin parámetros.
	 */
	private int myI;
	private int myN;
	private int myNo_skills;
	private byte[][] mySkills;
	private int myCover;
	private byte[] myCovered;
	private byte[] myAct;
	private byte[] myOpt;
	private int myOpt_elems;
	
    /**
     * Constructor con los valores a procesar. Se almacenan esos 
	 * parámetros en las variables de instancia.
     * 
     * @param myI
     * @param myN
     * @param myNo_skills
     * @param mySkills
     * @param myCover
     * @param myCovered
     * @param myAct
     * @param myOpt
     * @param myOpt_elems
     */
    public Cover(int myI, int myN, int myNo_skills, byte[][] mySkills,
			int myCover, byte[] myCovered, byte[] myAct, byte[] myOpt,
			int myOpt_elems) {
		super();
		this.myI = myI;
		this.myN = myN;
		this.myNo_skills = myNo_skills;
		this.mySkills = mySkills;
		this.myCover = myCover;
		this.myCovered = myCovered;
		this.myAct = myAct;
		this.myOpt = myOpt;
		this.myOpt_elems = myOpt_elems;
	}
    
    /**
     * Este método encapsula el proceso de creación de un objeto Cover y
	 * su agregado al pool. Retorna el Future del hilo.
	 * @return Future para poder hacer get().
	 * 
     * @param i
     * @param N
     * @param no_skills
     * @param skills
     * @param cover
     * @param covered
     * @param act
     * @param opt
     * @param opt_elems
     * @return
     */
    private static Future<Return> execute(int i, int n, int no_skills, 
    		byte[][] skills, int cover, byte[] covered, byte[] act, 
    		byte[] opt, int opt_elems) {
    	
    	Callable<Return> callable = new Cover(i, n, no_skills, skills, cover
    			, covered, act, opt, opt_elems);
    			
    	if (pool == null) {
    		pool = Executors.newCachedThreadPool();    	
    	}
		return pool.submit(callable);
    }
    	
    /**
	 * call() heredado de Callable. Llama al método que se hizo concurrente.
	 */
	@Override
	public Return call() throws Exception {		
		return try_it(this.myI, this.myN, this.myNo_skills, this.mySkills, 
				this.myCover, this.myCovered, this.myAct, this.myOpt, 
				this.myOpt_elems);		
	}

	int seq_do_try(int i, int N, int no_skills, byte[][] skills, int cover,
            byte[] covered, byte[] act, byte[] opt, int opt_elems) {
        int k, act_elems = 0;
        int opt_elems2;
        byte[] opt2;

        if (no_skills == cover) {
            for (k = 0; k < N; k++) {
                if (act[k] == 1)
                    act_elems++;
            }
            if (act_elems < opt_elems) {
                System.arraycopy(act, 0, opt, 0, N);
                opt_elems = act_elems;
            }
            return opt_elems;
        }

        if (i == N)
            return opt_elems;

        opt_elems2 = opt_elems;
        opt2 = (byte[]) opt.clone();

        // recursive call without the current element 
        opt_elems2 = seq_do_try(i + 1, N, no_skills, skills, cover, covered,
                act, opt2, opt_elems2);

        // recursive call with the current element 
        act[i] = 1;
        for (k = 0; k < no_skills; k++) {
            if (skills[i][k] == 1) {
                if (covered[k]++ == 0)
                    cover++;
            }
        }
        opt_elems = seq_do_try(i + 1, N, no_skills, skills, cover, covered,
                act, opt, opt_elems);

        // undo the setting of the current element
        act[i] = 0;
        for (k = 0; k < no_skills; k++)
            if (skills[i][k] == 1) {
                if (--covered[k] == 0) {
                    cover--;
                }
            }

        // take best result
        if (opt_elems2 < opt_elems) {
            opt_elems = opt_elems2;
            System.arraycopy(opt2, 0, opt, 0, N);
        }

        return opt_elems;
    }

	/**
	 * Se agrega el "throws" de las excepciones que puede llegar a lanzar
	 * el get() de los Future's.
	 */
    public Return try_it(int i, int N, int no_skills, byte[][] skills,
            int cover, byte[] covered, byte[] act, byte[] opt, 
            int opt_elems) throws InterruptedException, ExecutionException {
        int k, act_elems = 0;
        int opt_elems2;
        byte[] opt2;

        Return ret = new Return();
        ret.opt = opt;
        ret.opt_elems = opt_elems;

        if (no_skills == cover) {
            for (k = 0; k < N; k++) {
                if (act[k] == 1)
                    act_elems++;
            }
            if (act_elems < opt_elems) {
                //				System.arraycopy(act, 0, ret.opt, 0, N);
                ret.opt_elems = act_elems;
                ret.opt = (byte[]) act.clone();
            }
            return ret;
        }

        if (i == N)
            return ret;

        opt_elems2 = opt_elems;
        opt2 = (byte[]) opt.clone();

        /* recursive call without the current element */
        Return ret2;

        /**
		 * Se agrega nuevamente la condición, si todavía no alcanzamos el 
		 * umbral, se ejecuta la recursión de manera secuencial.
		 */
        if (i >= THRESHOLD) {
                
            ret2 = new Return();
            ret2.opt_elems = seq_do_try(i + 1, N, no_skills, skills, cover,
                    covered, act, opt2, opt_elems2);
            ret2.opt = opt2;

            //			ret2 = try_it(i+1, N, no_skills, skills, cover, 
            // 			covered, act, opt2, opt_elems2);

            /* recursive call with the current element */
            /* must copy all OBJECTS we modify! */
            byte[] act_copy = (byte[]) act.clone();
            byte[] covered_copy = (byte[]) covered.clone();

            act_copy[i] = 1;
            for (k = 0; k < no_skills; k++) {
                if (skills[i][k] == 1) {
                    if (covered_copy[k]++ == 0) {
                        cover++;
                    }
                }
            }

            ret.opt_elems = seq_do_try(i + 1, N, no_skills, skills, cover,
                    covered_copy, act_copy, ret.opt, ret.opt_elems);

            if (ret2.opt_elems < ret.opt_elems) {
                return ret2;
            }

            return ret;
        }
        
        /**
		 * Se agrega nuevamente éste bloque (al igual que en la versión 
		 * original) con las modificaciones necesarias para que se ejecute 
		 * en forma concurrente.
		 */        
        byte[] act_copy = (byte[]) act.clone();
        byte[] covered_copy = (byte[]) covered.clone();

        Future<Return> future1 = execute(i + 1, N, no_skills, skills, cover, 
        		covered, act, opt2, opt_elems2);
           
   
        /* recursive call with the current element */
        /* must use copies of all OBJECTS we modify! */

        act_copy[i] = 1;
        for (k = 0; k < no_skills; k++) {
            if (skills[i][k] == 1) {
                if (covered_copy[k]++ == 0) {
                    cover++;
                }
            }
        }
     
        Future<Return> future2 = execute(i + 1, N, no_skills, skills, cover, 
        		covered_copy, act_copy, ret.opt, ret.opt_elems);
        
        ret2 = future1.get();
        ret = future2.get();

        if (ret2.opt_elems < ret.opt_elems) {
            return ret2;
        }

        return ret;
    }

    public static void main(String[] args) {
        int no_skills = 0, no_elems;
        int opt_elms;
        OrcaRandom rand = new OrcaRandom();
        /**
		 * Se mueve la creación del objeto hasta tener los valores 
		 * necesarios.
		 */
        //Cover cover = new Cover();
        
        if (args.length == 0) {
            no_skills = 40;
        } else if (args.length == 1) {
            no_skills = Integer.parseInt(args[0]) * 2;
        } else {
            System.out.println("Usage: cover <size>");
            System.exit(1);
        }

        no_elems = no_skills / 2;

        byte[][] skills = new byte[no_elems][no_skills];

        for (int i = 0; i < no_elems; i++) {
            for (int j = 0; j < no_skills; j++) {
                byte c = (byte) ((rand.nextInt() % 1000) > 600 ? 1 : 0);
                skills[i][j] = c;
            }
        }

        byte[] act = new byte[no_skills];
        byte[] opt = new byte[no_skills];
        byte[] covered = new byte[no_skills];

        int opt_elems = no_elems + 1;

        /* output: opt and opt_elems */
        Return ret = new Return();
        
        System.out.println("cover (" + no_skills + " " + no_elems
                + ") started ");
        long start = System.currentTimeMillis();
        
        /**
		 * Ahora estoy en condiciones de crear el objeto con los parámetros
		 * correctos.
		 */
        Cover cover = new Cover(0, no_elems, no_skills, skills, 0, covered,
                act, opt, opt_elems);
        try {
        	/** Creo un pool simple donde agregar la tarea. */
        	ExecutorService pool = Executors.newSingleThreadExecutor();
        	/** Agrego la tarea */
        	Future<Return> future = pool.submit(cover);
        	/** Espero que el procesamiento termine */
			ret = future.get();
		} catch (Exception e) {
			e.printStackTrace();
		}
                
        long end = System.currentTimeMillis();
        double time = (end - start) / 1000.0;

        System.out.println("application time cover (" + no_skills + ","
                + no_elems + ") took " + time + " s");
        System.out.print("application result cover (" + no_skills + ","
                + no_elems + ") = ");

        if (ret.opt_elems == no_elems + 1) {
            System.out.println("A cover does not exist!");
        }

        String result = "";
        for (int i = 0; i < no_elems; i++) {
            if (ret.opt[i] == 1) {
                result = result + "Element " + i;
                for (int j = 0; j < no_skills; j++) {
                    result = result + (skills[i][j] == 1 ? "* " : "_ ");
                }
            }
        }
        System.out.println(result);

        if (args.length == 0) {
            if (!result
                    .equals("Element 0* _ * * * _ _ _ * _ * _ _ * * _ _ *" +
                    		" _ _ * * * _ _ _ _ _ _ _ _ _ * * _ _ _ _ * _" +
                    		" Element 2_ * _ _ _ _ * _ _ _ _ _ _ * _ _ _ " +
                    		"_ _ * _ * _ * _ _ _ _ * * _ * _ _ _ * * _ _ " +
                    		"* Element 5_ * _ _ _ _ _ * _ * _ * * _ _ * *" +
                    		" * _ _ _ _ * * _ * * _ _ * * _ * * * _ _ * _" +
                    		" _ Element 11_ * * * * * _ _ * _ * _ * * _ *" +
                    		" _ * * * * * _ _ * _ _ * * _ _ _ _ _ * * _ *" +
                    		" _ _ ")) {
            	
                System.out.println("Test failed!");
                System.exit(1);
            } else {
                System.out.println("Test succeeded!");
            }
        }
        /**
    	 * Salgo con exit() porque sinó no sale.
    	 */
    	System.exit(0);
    }    
}